1. Field of the Invention
The present invention relates to an improved scan interleaving method based on context values of neighboring pixels, an improved binary shape encoding/decoding method, and an encoding/decoding apparatus suitable for the same.
2. Description of the Related Art
Scan interleaving methods, which are used to encode/decode binary images require multipurpose encoding/decoding functions such as adjustment of resolution or image quality, encoding/decoding to resist transmission errors, or transmission rate adjustment.
FIG. 1 illustrates a conventional concept of an encoder and a decoder. In FIG. 1, a shape encoder 11 encodes input shape data, and sends an encoded bit stream 13 to a shape decoder 15. The shape decoder 15 restores the shape data from the transmitted bit stream.
However, in consideration of the resolution or image quality of a shape to be encoded, the shape encoder 11 shown in FIG. 1 generates a great number of bits by performing encoding, thus increasing system complexity. This problem becomes serious in multipurpose encoding/decoding of binary images in the video communications field in which various additional functions such as adjustment of resolution or image quality, encoding/decoding to resist transmission errors, or transmission rate adjustment are required.
To overcome this problem, a so-called scan interleaving method is used, in which a pixel of a current scanning line is encoded/decoded through an XOR operation by referring to the immediately preceding and succeeding scanning lines of the current scanning line.
According to the scan interleaving (SI) method, if the pixel of the current scanning line and those of the immediately preceding and succeeding scanning lines of the current scanning line are all the same value, the current pixel is not encoded. The current pixel is only encoded when they are different from one another. In order to determine whether the pixel of the current scanning line and those of the immediately preceding and succeeding scanning lines of the current scanning line are all the same value, an XOR operation is performed.
FIG. 2 is a view for illustrating a conventional scan interleaving method. In FIG. 2, reference numeral 200 denotes original shape data, reference numeral 210 denotes base image data, and reference numeral 220 denotes object image data to be scan-interleaved.
The base image data is composed of pixels on odd (or even) numbered scanning lines among pixels forming the original shape data 200.
The object image data 220 is composed of pixels on even (or odd) numbered scanning lines among the pixels forming the original shape data 200, and includes transitional sample data (TSD) and exceptional sample data (ESD), and predictive sample data (PSD).
The TSD, which are denoted by squares, indicate pixels for which the pixel on a current scanning line is the same as only one of the corresponding pixels on the preceding and succeeding scanning lines as shown in the object image data 220 of FIG. 2. For example, the third pixel from the left on the first scanning line of the object image data 220 is different to only one of the third pixels from the left on the first and second scanning lines of the base image data 210. Thus, the TSD in this case is xe2x80x9c1xe2x80x9d. This is obtained by performing an XOR operation on the pixel on the current scanning line with the corresponding pixel on the preceding line, then, an XOR operation on the pixel of the current line with the corresponding pixel of the succeeding line, and finally an XOR operation on the two XOR results.
The ESD, which are denoted by circles, indicate pixels for which the pixel on the current scanning line is different to both of the corresponding pixels on the preceding and succeeding scanning lines as shown in the object image data 240 of FIG. 2. For example, the third pixel from the right of the first scanning line in the object image data 220 is different to both of the third pixels from the right of the first and second scanning lines in the base image data 210. Thus, the ESD in this case is xe2x80x9c0xe2x80x9d by performing an XOR operation on the third pixel from the right on the current scanning line with the corresponding pixel on the preceding line, then, an XOR operation on the pixel on the current line with the corresponding pixel on the succeeding line, and finally an XOR operation on the two XOR results.
The PSD are all the pixels except the TSD (230) and the ESD (240) pixels in the object image data (220).
In the scan interleaving method, the base image data is independently encoded from the object image data. In encoding the object image data, a pixel context value is determined by the condition of adjacent pixels, and the object image data is entropy-encoded based on a probability model dependent on pixel context value.
The ESD is divided into continuous data and noncontinuous data, and then encoded. In the latter, the pixel prediction probability of the context and the occurrence run of the value of the ESD are entropy-encoded.
In the former, the pixel prediction probability of the context and the continuous segments of the first data value of the successive ESD are encoded.
However, the conventional scan interleaving method performs TSD encoding and ESD encoding in two separate steps, thus increasing the algorithm complexity and making implementation difficult.
In addition, the overall encoding performance is decreased due to encoding the ESD.
To solve the above problems, it is a first object of the present invention to provide an improved scan interleaving method for selectively encoding a part or the whole of object image data according to presence or absence of ESD.
It is a second object of the present invention to provide an improved scan interleaving method for increasing the overall coding efficiency by determining an optimum scan interleaving direction.
It is a third object of the present invention to provide a hierarchical binary shape encoding method.
It is a fourth object of the present invention to provide an encoding apparatus suitable for the hierarchical binary shape encoding method.
It is a fifth object of the present invention to provide a hierarchical binary shape decoding method.
It is a sixth object of the present invention to provide a decoding apparatus suitable for the hierarchical binary shape decoding method.
To achieve the above first object, there is provided a scan interleaving method for obtaining base image data and object image data to be encoded including TSD, ESD and PSD by scan-interleaving binary image data, and encoding the obtained base image data, and object image data which includes TSD, ESD and PSD, including the steps of (a) receiving the binary image data, (b) scan-interleaving the received binary image data, (c) obtaining the base image data from the scan-interleaving result, (d) obtaining the object image data from the scan-interleaving result, (e) encoding the base image data obtained in said step (d), (f) determining whether the object image data obtained in said steps (a) through (e) includes ESD, (g) encoding TSD only when there is no ESD, and (h) encoding TSD, ESD and PSD when there is ESD.
To achieve the second object, there is provided a scan interleaving method for obtaining base image data and object image data including TSD, ESD and PSD by scan-interleaving binary image data, and encoding the obtained base image data, and TSD, ESD and PSD, including the steps of (axe2x80x2) receiving the binary image data, (bxe2x80x2) determining a scan interleaving direction for the received binary image data, (cxe2x80x2) scan interleaving the received binary data in the determined scan interleaving direction, (dxe2x80x2) obtaining the base image data from the scan-interleaving result, (exe2x80x2) obtaining the object image data from the scan-interleaving result, (fxe2x80x2) encoding the base image data obtained in step (dxe2x80x2), (gxe2x80x2) determining whether the object image data includes ESD, (hxe2x80x2) encoding TSD only when there is no ESD, and (ixe2x80x2) encoding the TSD and ESD when there is ESD.
To achieve the third object, there is provided a hierarchical binary shape encoding method including the steps of retrieving a base layer from the current binary shape data, encoding the base layer by an arbitrary encoding method, and encoding an enhancement layer having the current binary shape data by referring to the base layer or a preceding frame.
To achieve the fourth object, there is provided an apparatus for encoding binary shape data including a portion for down-sampling for SI method, the portion for performing down-sampling for SI method on the binary shape data to form a base layer, a portion for encoding the base layer supplied from the down-sampling portion, and a portion for encoding an enhancement layer having the current binary shape data by referring to the base layer or a preceding frame.
To achieve the fifth object, there is provided a method for decoding binary shape data having a base layer bitstream and an enhancement layer bitstream including the steps of decoding the base layer from the base layer bitstream, performing up-sampling for SI method on the base layer restored in the base layer decoding step, decoding an enhancement layer from the enhancement layer bitstream by referring to the base layer or the preceding frame, and determining whether restoration of additional spatial layers is necessary, and if necessary, and applying the shape data as restored to the up-sampling step for the purpose of referring to the same in the decoding step of the next enhancement layer.
To achieve the sixth object, there is provided an apparatus for decoding binary shape data having a base layer bitstream and an enhancement layer bitstream, including a base layer decoding portion for decoding the base layer from the base layer bitstream, an up-sampling portion for performing up-sampling for SI method on the base layer restored by the base layer decoding portion, decoding an enhancement layer from the enhancement layer bitstream by referring to the base layer or the preceding frame, and an enhancement layer decoding portion for decoding an enhancement layer from the enhancement layer bitstream.